# 题目：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树，假设输入的前序遍历和中序遍历的结构都不包含重复的数字

# 通过前序遍历知道根节点，通过中序遍历知道左子树与右子树
# 可以通过递归的方法解决
from provate import TreeNode
import  provate
import typing


def construct(preorder, inorder):
    if len(preorder) == 0 or len(inorder) == 0 or len(preorder) != len(inorder):
        print('input ERROR ')
        return None
    return construct_core(preorder, inorder)


def construct_core(preorder: list, inorder: list):
    if len(preorder) != len(inorder) or len(preorder) <= 0 or len(inorder) <= 0:
        return None
    root_value = preorder[0]
    root = TreeNode(root_value)

    if len(preorder) == 1:
        return root

    else:
        cur_inorder = inorder.index(root_value)
        leftchild_length = cur_inorder
        # rightchild_length = len(inorder) - cur_inorder - 1
        root.leftchild = construct_core(preorder[1:1 + leftchild_length], inorder[:cur_inorder])
        root.rightchild = construct_core(preorder[1 + leftchild_length:], inorder[cur_inorder + 1:])

    return root


if __name__ == '__main__':
    preorder = [1, 2, 4, 7, 3, 5, 6, 8]
    inorder = [4, 7, 2, 1, 5, 3, 8, 6]

    root = construct(preorder, inorder)
    provate.preorder(root)


